#include <unordered_set>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <cassert>
#include <limits>
#include <ctime>
#include <bitset>
#include <random>

using namespace std;

/**
* ***************************************************************************************************************
* @brief 类
* ***************************************************************************************************************
*/
class Node {
public:
    int id;
    int p;
    unordered_set<int> neighbors;

    int pCopy;

    Node() {};
    Node(int id, int p): id(id), p(p), pCopy(p) {};

    void back() {
        p = pCopy;
    }
};

class Edge {
public:
    int id;
    int u, v, capacity;
    uint64_t channels0 = 0;  // 记录当前占用，从下标0开始
    uint64_t channels1 = 0;  // 记录重复占用，从下标0开始
    bool isDown = false;

    uint64_t channelsCopy = 0;

    Edge() {};
    Edge( int id, int u, int v, int capacity): id(id), u(u), v(v), capacity(capacity) {};

    void back() {
        isDown = false;
        channels0 = channelsCopy;
        channels1 = 0;
    };

    void costChannels(int start, int width) {
        uint64_t mask = ((1ULL << width) - 1) << (start - 1);
        if ((mask & channels0) != 0)
            channels1 |= (mask & channels0);
        channels0 |= mask;
    }

    void releaseChannels(int start, int width) {
        uint64_t mask = ((1ULL << width) - 1) << (start - 1);
        channels0 &= ~mask;
        channels0 |= channels1;
        channels1 &= (mask ^ channels1);
    }
};

class Business {
public:
    int start, end, width, value, id;
    vector<int> edgePath;
    vector<int> nodePath;
    vector<int> costStartChannels;
    unordered_set<int> usedPNode;

    vector<int> nodePathCopy;
    vector<int> edgePathCopy;
    vector<int> costStartChannelsCopy;

    Business() {};
    Business(int id, int start, int end, int sW, int eW, int value, int lenEdge):
        id(id), start(start), end(end), width(eW-sW+1), value(value) {

        for (int i = 0; i < lenEdge; ++i) {
            costStartChannels.emplace_back(sW);
        }
        costStartChannelsCopy = costStartChannels;
    }

    void back() {
        costStartChannels = costStartChannelsCopy;
        edgePath = edgePathCopy;
        nodePath = nodePathCopy;
        usedPNode.clear();
    }

    void updateP() {
        usedPNode.clear();
        for (int i = 1; i < costStartChannels.size(); ++i) {
            if (costStartChannels[i-1] != costStartChannels[i])
                usedPNode.insert(nodePath[i]);
        }
    }
};

/**
* ***************************************************************************************************************
* @brief 全局变量
* ***************************************************************************************************************
*/
int N, M;
int capacity = 40;
int fixedCount = 0;
int fixedValue = 0;
int currentValue = 0;
int ORIGIN_VALUE = 0;
unordered_map<int, Node> NodeID_Node;
unordered_map<int, Edge> EdgeID_Edge;
unordered_map<int, Business> BusID_Bus;
vector<vector<unordered_set<int>>> Graph;

int INF = 1e9; // 无穷大
bool needAssert = false;
float score;

// 超参数
float PATH_LEN_EXPANSION = 1.2;

/**
* ***************************************************************************************************************
* @brief 通用函数
* ***************************************************************************************************************
*/
int findElementIndex(const vector<int>& vec, const int& element) {
    auto it = find(vec.begin(), vec.end(), element);
    if (it != vec.end()) {
        return distance(vec.begin(), it);
    }
    else {
        return -1;
    }
}

int findContinueIndex(uint64_t pre, const int& w) {
    uint64_t mask = (1ULL << w) - 1;
    for (int i = 0; i <= 40 - w; ++i) {
        if ((pre & mask) == 0) {
            return i + 1;
        }
        pre >>= 1;
    }
    return -1;
}

//unordered_set<int> findAllContinueIndex(uint64_t channels, const int &width)
//{
//    const uint64_t mask = (1ULL << width) - 1;
//    unordered_set<int> startChannels;
//
//    for (int i = 1; i <= 40 - width + 1; ++i)
//    {
//        if ((channels & mask) == 0)
//            startChannels.emplace(i);
//        channels >>= 1;
//    }
//    return startChannels;
//}
vector<int> findAllContinueIndex(uint64_t channels, const int& width)
{
    const uint64_t mask = (1ULL << width) - 1;
    vector<int> startChannels;

    for (int i = 1; i <= 40 - width + 1; ++i)
    {
        if ((channels & mask) == 0)
            startChannels.emplace_back(i);
        channels >>= 1;
    }
    return startChannels;
}

void printLow40Bits(uint64_t number) {
    const int bitsToPrint = 40;

    uint64_t low40Bits = number & ((1ULL << bitsToPrint) - 1);

    // 将低 40 位转换为二进制字符串
    bitset<bitsToPrint> bitsetLow40(low40Bits);
    string bitString = bitsetLow40.to_string();

    cout << bitString << endl;
}
/**
* ***************************************************************************************************************
* @brief 路径搜索函数
* 1. 提高路径搜索的成功率：(1)压缩时间，增大可搜索范围
* 2. 减少资源占用率
* ***************************************************************************************************************
*/
unordered_map<int, int> getDistance(const int& end, const Business& failedBus) {
    unordered_set<int> visited = { end };
    unordered_map<int, int> dis = {{end, 0}};

    queue<int> q;
    q.emplace(end);

    while (!q.empty()) {
        int src = q.front();
        q.pop();

        unordered_set<int>& neighbors = NodeID_Node[src].neighbors;
        for (const int& neighbor : neighbors) {
            if (visited.find(neighbor) != visited.end()) continue;

            bool isOK = false;
            for (int eId : Graph[src][neighbor]) {
                Edge& edge = EdgeID_Edge[eId];
                if (edge.isDown) continue;
                if (findElementIndex(failedBus.edgePath, eId) == -1 && findContinueIndex(edge.channels0, failedBus.width) == -1)
                    continue;
                isOK = true;
                break;
            }
            if (!isOK) continue;

            visited.insert(neighbor);
            dis[neighbor] = dis[src] + 1;
            q.emplace(neighbor);
        }
    }
    return dis;
}

bool isNodeInPath(const vector<int>& path, const int& nodeId) {
    for (int i = 0; i < path.size(); i += 2)
    {
        if (path[i] == nodeId)
            return true;
    }
    return false;
}

uint64_t getEdgeChannels(const int eId, const Business& business) {
    Edge &edge = EdgeID_Edge[eId];
    uint64_t channels = edge.channels0;

    int idx = findElementIndex(business.edgePath, edge.id);
    if (idx != -1)
    {
        uint64_t mask = ((1ULL << business.width) - 1) << (business.costStartChannels[idx] - 1);
        channels &= ~mask;
    }
    return channels;
}

uint64_t canConnect(const Edge& edge, const uint64_t& lastChannels, const Business& failedBus, const bool& isNotUsePNode, const int& nodeP) {
    uint64_t channels = getEdgeChannels(edge.id, failedBus);

    if (needAssert) assert(nodeP >= 0);

    if (nodeP == 0 && isNotUsePNode)
        channels |= lastChannels;

    if (findContinueIndex(channels, failedBus.width) == -1) return numeric_limits<uint64_t>::max();
    else return channels;
}

void getNPathAndEPath(const vector<int>& path, vector<int>& nPath, vector<int>& ePath) {
    for (int i = 0; i < path.size(); ++i) {
        if (i % 2 == 0) nPath.emplace_back(path[i]);
        else ePath.emplace_back(path[i]);
    }
}

struct CustomComparator
{
    bool operator()(const vector<int> &a, const vector<int> &b)
    {
        if (a[0] == b[0])
            return a[1] < b[1];
        return a[0] > b[0];
    }
};

vector<pair<int, int>> findBestChannels(const vector<int>& path, const Business& bus) {
    vector<int> nPath;
    vector<int> ePath;
    getNPathAndEPath(path, nPath, ePath);

    int numEdges = ePath.size();
    int finalStartChannel = -1;
    int finalDist = INF;
    bool isFound = false;

    priority_queue<vector<int>, vector<vector<int>>, CustomComparator> pq;  // <dist, edgeIdx, startChannel>
    vector<vector<int>> dist(numEdges, vector<int>(capacity+1, INF));  // edgeIdx<startChannel<dist>>
    vector<vector<int>> prev(numEdges, vector<int>(capacity+1, -1));           // edgeIdx<startChannel<lastStartChannel>>

    // *********************************************initiate the priority queue**************************************************
    const vector<int>& startChannels = findAllContinueIndex(getEdgeChannels(ePath[0], bus), bus.width);
    for (int start : startChannels)
    {
        pq.push({0, 0, start});
    }
    // *************************************************************************************************************************

    while (!pq.empty() && !isFound) {
        const vector<int>& vec = pq.top();
        int lastDist = vec[0];
        int lastEdgeIdx = vec[1];
        int lastStart = vec[2];
        pq.pop();

        if (lastEdgeIdx == numEdges - 1) {
            finalStartChannel = lastStart;
            finalDist = lastDist;
            break;
        }

        int nextEdgeIdx = lastEdgeIdx + 1;
        Node &nextNode = NodeID_Node[nPath[nextEdgeIdx]];
        uint64_t nextChannels = getEdgeChannels(ePath[nextEdgeIdx], bus);
        const vector<int>& nextStartChannels = findAllContinueIndex(nextChannels, bus.width);
        bool isUsePNode = bus.usedPNode.find(nextNode.id) != bus.usedPNode.end();

        for (int nextStart : nextStartChannels) {
            int newDist;
            if (nextNode.p > 0 || isUsePNode)
                newDist = (lastStart == nextStart) ? lastDist : lastDist + 1;
            else
                newDist = (lastStart == nextStart) ? lastDist : INF;

            if (newDist < dist[nextEdgeIdx][nextStart]) {
                dist[nextEdgeIdx][nextStart] = newDist;
                pq.push({newDist, nextEdgeIdx, nextStart});
                prev[nextEdgeIdx][nextStart] = lastStart;

                if (nextEdgeIdx == ePath.size() - 1) {
                    finalStartChannel = nextStart;
                    finalDist = newDist;
                    isFound = true;
                    break;
                }
            }
        }
    }

    if (needAssert) assert(finalStartChannel != -1);

    vector<pair<int, int>> bestChannels; // <start, edgeId>
    for (int i = numEdges - 1; i >= 0; --i)
    {
        int edgeId = ePath[i];
        bestChannels.emplace_back(finalStartChannel, edgeId);
        finalStartChannel = prev[i][finalStartChannel];
    }
    reverse(bestChannels.begin(), bestChannels.end());
    return bestChannels;
}

vector<pair<int, int>> findAllPaths(const Edge& failedEdge, const Business& failedBus, int maxIter=3000) {
    deque<pair<vector<int>, uint64_t>> q;  // {node, edge, node, edge, ...}, channels
    unordered_map<int, int> distance = getDistance(failedBus.end, failedBus);
    int iterCount = 0;
    q.push_back({{failedBus.start}, 0});

    int originPathSize = failedBus.nodePath.size() * 2;
    float expectedPathSize  = 2 * (float)failedBus.value / (float)currentValue * (float)(M) * (40 / (float)failedBus.width);

    while (!q.empty() && iterCount < maxIter) {
        ++iterCount;
        auto& p = q.front();
        const vector<int> path = p.first;
        uint64_t lastChannels = p.second;
        q.pop_front();

        if (path.size() > originPathSize * PATH_LEN_EXPANSION && path.size() > expectedPathSize) continue;

        int lastNode = path.back();
        bool isNotUsePNode = failedBus.usedPNode.find(lastNode) == failedBus.usedPNode.end();
        unordered_set<int>& neighbors = NodeID_Node[lastNode].neighbors;

        for (const int neighbor : neighbors) {
            //*****************************pass nodes in the path****************************
            if (isNodeInPath(path, neighbor))
                continue;
            //*******************************************************************************

            for (int eId : Graph[lastNode][neighbor]) {
                Edge& edge = EdgeID_Edge[eId];
                if (edge.isDown) continue;

                //*******************************check whether the edge is capable*******************************
                uint64_t channels = canConnect(edge, lastChannels, failedBus, isNotUsePNode, NodeID_Node[lastNode].p);
                if (channels == numeric_limits<uint64_t>::max())
                    continue;
                //***********************************************************************************************

                vector<int> newPath(path);
                newPath.emplace_back(eId);
                newPath.emplace_back(neighbor);

                if (neighbor == failedBus.end) {
                    const vector<pair<int, int>>& result = findBestChannels(newPath, failedBus);
                    if (needAssert) assert(!result.empty());
                    return result;
                } else {
                    if (distance[neighbor] < distance[lastNode] && newPath.size() < failedBus.nodePath.size() * 2 * PATH_LEN_EXPANSION) {
                        q.emplace_front(newPath, channels);
                    } else {
                        q.emplace_back(newPath, channels);
                    }
                }
            }
        }
    }

    return {};
}

/**
* ***************************************************************************************************************
* @brief 检查函数
* ***************************************************************************************************************
*/
void check(const vector<pair<int, int>>& startChannels, const Business& newBus, const Business& oldBus) {
    for (const auto& p : startChannels) {
        int startChannel = p.first;
        int edgeId = p.second;
        Edge& edge = EdgeID_Edge[edgeId];

        // 是否经过坏边
        assert(!edge.isDown);

        // 选择的channel是否合理
        assert(1 <= startChannel && startChannel <= capacity - oldBus.width + 1);

        // 检查边占用是否冲突
        uint64_t mask1 = ((1ULL << oldBus.width) - 1) << (startChannel - 1);
        uint64_t channels = edge.channels0;
        int idx = findElementIndex(oldBus.edgePath, edgeId);
        if (idx != -1) {
            uint64_t mask2 = ((1ULL << oldBus.width) - 1) << (oldBus.costStartChannels[idx] - 1);
            channels &= ~mask2;
        }
        assert((channels & mask1) == 0);
    }
}

/**
* ***************************************************************************************************************
* @brief 自定义数据集生成函数
* ***************************************************************************************************************
*/
/**
 * Jaccard Similarity: 计算两个序列的相似度（交集除以并集）
 */
float JaccardSimilarity(const vector<int>& seq1, const vector<int>& seq2) {
    if (seq1.empty() || seq2.empty()) return 0;

    unordered_set<int> set1(seq1.begin(), seq1.end());
    unordered_set<int> set2(seq2.begin(), seq2.end());
    // 计算交集
    size_t intersectionSize = 0;
    for (const auto& elem : set1) {
        if (set2.find(elem) != set2.end()) {
            ++intersectionSize;
        }
    }
    // 计算并集
    size_t unionSize = set1.size() + set2.size() - intersectionSize;
    // 返回交集大小除以并集大小（类型转换为浮点数）
    return float(intersectionSize) / float(unionSize);
}

void reorder(const vector<int>& original, vector<int>& subset) {
    // 创建一个哈希表来存储每个元素在原始序列中的位置
    unordered_map<int, int> positionMap;
    for (int i = 0; i < original.size(); ++i) {
        positionMap[original[i]] = i;
    }

    // 使用lambda函数对子集进行排序
    sort(subset.begin(), subset.end(), [&positionMap](int a, int b) {
        return positionMap[a] < positionMap[b];
    });
}

vector<vector<int>> generateSeqs(
        const vector<int>& numbers, int maxGroupNum=50, float maxSimilarity=0.6, int maxLen=50, int minLen=10, bool order=false) {
    assert(maxLen >= minLen);

    vector<vector<int>> seqGroups(maxGroupNum);

    int idx = 0;
    while (true) {
        bool isSomeGroupOK = false; // 当遍历完所有组，都没有插入成功的（仍然为false），则退出循环

        for (int i = 0; i < maxGroupNum; ++i) {
            vector<int>& seq = seqGroups[i];

            assert(seq.size() <= maxLen);
            if (seq.size() == maxLen) continue;

            int iter = seq.size() < minLen ? minLen - int(seq.size()) : 1;
            for (int k = 0; k < iter; ++k) {
                bool isAllNumberFailed = true;
                for (int j = 0; j < numbers.size(); ++j) {

                    int n;
                    if (order) n = numbers[j];
                    else n = numbers[idx];

                    ++idx;
                    if (idx == numbers.size()) idx = 0;

                    if (findElementIndex(seq, n) == -1) seq.emplace_back(n);
                    else continue;

                    bool valid = all_of(seqGroups.begin(), seqGroups.end(), [&](vector<int>& other) {
                        if (&seq == &other) return true;
                        else return JaccardSimilarity(seq, other) <= maxSimilarity;
                    });

                    if (valid) {
                        isSomeGroupOK = true;
                        isAllNumberFailed = false;
                        break;
                    } else {
                        seq.pop_back();
                    }
                }
                if (isAllNumberFailed) break;
            }

        }
        if (!isSomeGroupOK) break;
    }

    for (vector<int>& seq : seqGroups) {
        reorder(numbers, seq);
    }

    return seqGroups;
}

void outputData(const vector<vector<int>>& seqGroups) {
    cout << seqGroups.size() << endl;
    for (const vector<int>& seq : seqGroups) {
        cout << seq.size() << endl;
        for (const int& e : seq) cout << e << " ";
        cout << endl;
    }
}

unordered_map<int, int> countEdgeMaxWidth() {
    unordered_map<int, int> edgeId_maxWidth;

    for (auto& p : EdgeID_Edge) {
        int eId = p.first;
        edgeId_maxWidth[eId] = 0;
    }

    for (auto& p : BusID_Bus) {
        Business& bus = p.second;
        for (int eId : bus.edgePath) {
            if (bus.width > edgeId_maxWidth[eId]) edgeId_maxWidth[eId] = bus.width;
        }
    }

    return edgeId_maxWidth;
}

unordered_map<int, int> countEdgesNodeP() {
    unordered_map<int, int> edgeId_countNodeP;

    for (auto &p : EdgeID_Edge) {
        Edge& edge = p.second;
        Node& UNode = NodeID_Node[edge.u];
        Node& VNode = NodeID_Node[edge.v];

        edgeId_countNodeP[edge.id] = UNode.p + VNode.p;
    }
    return edgeId_countNodeP;
}

unordered_map<int, int> countEdgesNeighbors() {
    unordered_map<int, int> edgeId_countNeighbors;

    for (auto &p : EdgeID_Edge) {
        Edge& edge = p.second;
        Node& UNode = NodeID_Node[edge.u];
        Node& VNode = NodeID_Node[edge.v];

        int countNeighbors = 0;
        for (int neighborNId : UNode.neighbors) {
            countNeighbors += int(Graph[UNode.id][neighborNId].size());
        }
        for (int neighborNId : VNode.neighbors) {
            countNeighbors += int(Graph[VNode.id][neighborNId].size());
        }
        edgeId_countNeighbors[edge.id] = countNeighbors;
    }
    return edgeId_countNeighbors;
}

unordered_map<int, int> countEdgesLeftChannels() {
    unordered_map<int, int> edgeId_countLC;
    for (auto &p : EdgeID_Edge) {
        Edge &edge = p.second;
        const vector<int>& startChannels = findAllContinueIndex(edge.channels0, 1);
        edgeId_countLC[edge.id] = startChannels.size();
    }
    return edgeId_countLC;
}

// 按顺序生成序列，仅在测试时用
vector<int> generateOrderedSequence(const int& M) {
    vector<int> seq(M);
    iota(seq.begin(), seq.end(), 1);
    return seq;
}

void generateData() {
    int groupNum=30;
    float maxSimilarity=0.49;
    int maxLen=min(60, M / 1);
    int minLen=min(60, M / 1);
    int order=true;
    int topK = M / 2;

    // ******************************************** sort edges ************************************************
    unordered_map<int, int> edgeId_countLC = countEdgesLeftChannels();
//    unordered_map<int, int> edgeId_countNeighbors = countEdgesNeighbors();
    unordered_map<int, int> edgeId_maxWidth = countEdgeMaxWidth();
    unordered_map<int, int> edgeId_countNodeP = countEdgesNodeP();
    vector<int> edgeIds = generateOrderedSequence(M);
    sort(edgeIds.begin(), edgeIds.end(), [&](int aId, int bId) { // 返回true则越靠前
        // 策略1
//        if (edgeId_countLC[aId] == edgeId_countLC[bId]) {
////            return edgeId_countNeighbors[aId] > edgeId_countNeighbors[bId];
////            return false;
//        }
//        return edgeId_countLC[aId] > edgeId_countLC[bId];

//        // 策略2
//        if (edgeId_countNodeP[aId] == edgeId_countNodeP[bId]) {
//            return edgeId_countLC[aId] > edgeId_countLC[bId];
//        }
//        return  edgeId_countNodeP[aId] < edgeId_countNodeP[bId];

        // 策略3
        if (edgeId_countNodeP[aId] == edgeId_countNodeP[bId]) {
            if (edgeId_maxWidth[aId] == edgeId_maxWidth[bId]) {
                return edgeId_countLC[aId] > edgeId_countLC[bId];
            }
            return edgeId_maxWidth[aId] < edgeId_maxWidth[bId];
        }
        return edgeId_countNodeP[aId] < edgeId_countNodeP[bId];
    });
    vector<int> topKEdgeIds(edgeIds.begin(), edgeIds.begin() + topK);

////     策略4
//    vector<int> numbers = generateOrderedSequence(M);
    // ********************************************************************************************************

    const vector<vector<int>>& seqGroups = generateSeqs(topKEdgeIds, groupNum, maxSimilarity, maxLen, minLen, order);

    outputData(seqGroups);
}

/**
* ***************************************************************************************************************
* @brief 函数
* ***************************************************************************************************************
*/
void setNodePath(Business& bus) {
    int nodeId = bus.start;
    bus.nodePath.emplace_back(nodeId);
    bus.nodePathCopy.emplace_back(nodeId);

    for (int edgeId : bus.edgePath) {
        Edge& edge = EdgeID_Edge[edgeId];
        int u = edge.u;
        int v = edge.v;
        if (nodeId == u) {
            bus.nodePath.emplace_back(v);
            bus.nodePathCopy.emplace_back(v);
            nodeId = v;
        } else {
            bus.nodePath.emplace_back(u);
            bus.nodePathCopy.emplace_back(u);
            nodeId = u;
        }
    }
}

void costChannels(const Business& bus) {
    for (int i = 0; i < bus.edgePath.size(); ++i) {
        int edgeId = bus.edgePath[i];
        Edge& edge = EdgeID_Edge[edgeId];
        edge.costChannels(bus.costStartChannels[i], bus.width);
        edge.channelsCopy = edge.channels0;
    }
}

void back() {
    for (auto& entry : BusID_Bus) {
        Business& bus = entry.second;
        bus.back();
    }
    for (auto& entry : NodeID_Node) {
        Node& node = entry.second;
        node.back();
    }
    for (auto& entry : EdgeID_Edge) {
        Edge& edge = entry.second;
        edge.back();
    }

    score += float(currentValue) / float(ORIGIN_VALUE) * 10000;
    currentValue = ORIGIN_VALUE;
}

vector<int> findFailedBusIds(const int& failedEdgeId, const unordered_set<int>& abandonedBusIds) {
    vector<int> failedBusIds;
    for (auto& entry : BusID_Bus) {
        Business& bus = entry.second;
        if (abandonedBusIds.find(bus.id) == abandonedBusIds.end() && find(bus.edgePath.begin(), bus.edgePath.end(), failedEdgeId) != bus.edgePath.end()) {
            failedBusIds.emplace_back(bus.id);
            currentValue -= bus.value;
        }
    }
    return failedBusIds;
}

void updateBusiness(const vector<pair<int, int>>& startChannelsAndEdgeIds, Business& bus) {
    int src = bus.start;
    vector<int> newNodePath{ src } ;
    vector<int> newEdgePath;
    vector<int> newCostStartChannels;

    for (auto& p : startChannelsAndEdgeIds) {
        int startChannel = p.first;
        int edgeId = p.second;
        newCostStartChannels.emplace_back(startChannel);
        newEdgePath.emplace_back(edgeId);
        Edge& edge = EdgeID_Edge[edgeId];
        if (edge.u == src) {
            newNodePath.emplace_back(edge.v);
            src = edge.v;
        } else {
            newNodePath.emplace_back(edge.u);
            src = edge.u;
        }
    }

    bus.edgePath = newEdgePath;
    bus.nodePath = newNodePath;
    bus.costStartChannels = newCostStartChannels;
    bus.updateP();
}

void updateGraph(const Business& newBus, const Business& oldBus) {
    for (int i = 0; i < newBus.edgePath.size(); ++i) {
        int edgeId = newBus.edgePath[i];
        Edge& edge = EdgeID_Edge[edgeId];
        edge.costChannels(newBus.costStartChannels[i], newBus.width);
        if (i > 0 && newBus.costStartChannels[i-1] != newBus.costStartChannels[i]) {
            int nodeId = newBus.nodePath[i];
            if (oldBus.usedPNode.find(nodeId) == oldBus.usedPNode.end()) {
                Node& node = NodeID_Node[nodeId];
                --node.p;
            }
        }
    }
}

void releaseResource(const Business& newBus, const Business& oldBus) {
    for (int i = 0; i < oldBus.edgePath.size(); ++i) {
        int edgeId = oldBus.edgePath[i];
        Edge& edge = EdgeID_Edge[edgeId];
        edge.releaseChannels(oldBus.costStartChannels[i], oldBus.width);
        if (i > 0 && oldBus.costStartChannels[i-1] != oldBus.costStartChannels[i]) {
            int nodeId = oldBus.nodePath[i];
            if (newBus.usedPNode.find(nodeId) == newBus.usedPNode.end()) {
                Node& node = NodeID_Node[nodeId];
                ++node.p;
            }
        }
    }
}

void outputResult(const Business& bus) {
    cout << bus.id << " " << bus.edgePath.size() << endl;

    for (int i = 0; i < bus.edgePath.size(); ++i) {
        int startChannel = bus.costStartChannels[i];
        cout << bus.edgePath[i] << " " << startChannel << " " << startChannel + bus.width - 1 << " ";
    }

    cout << endl;
    fflush(stdout);

}

void fixFailedEdge(const int& failedEdgeId, unordered_set<int>& abandonedBusIds) {
    Edge& failedEdge = EdgeID_Edge[failedEdgeId];
    failedEdge.isDown = true;
    vector<Business> releasedBusinesses;
    vector<Business> fixedBusinesses;
    vector<int> failedBusIds = findFailedBusIds(failedEdgeId, abandonedBusIds);

    sort(failedBusIds.begin(), failedBusIds.end(), [](const int a, const int b) {
        Business& aBus = BusID_Bus[a];
        Business& bBus = BusID_Bus[b];
        return aBus.value > bBus.value;
    });

    for (int busId : failedBusIds) {
        Business& failedBus = BusID_Bus[busId];

        vector<pair<int, int>> startChannelsAndEdgeIds = findAllPaths(failedEdge, failedBus);

        if (!startChannelsAndEdgeIds.empty()) {
            Business failedBusCopy = failedBus;

            updateBusiness(startChannelsAndEdgeIds, failedBus);
            if (needAssert) check(startChannelsAndEdgeIds, failedBus, failedBusCopy);
            updateGraph(failedBus, failedBusCopy);

            releasedBusinesses.emplace_back(failedBusCopy);
            fixedBusinesses.emplace_back(failedBus);
        } else {
            abandonedBusIds.emplace(failedBus.id);
        }
    }

    for (int i = 0; i < releasedBusinesses.size(); ++i) {
        releaseResource(fixedBusinesses[i], releasedBusinesses[i]);
    }

    fixedCount += int(fixedBusinesses.size());
    cout << fixedBusinesses.size() << endl;
    for (const Business& bus : fixedBusinesses) {
        fixedValue += bus.value;
        currentValue += bus.value;
        outputResult(bus);
    }
}

/**
* ***************************************************************************************************************
* @brief 主函数
* ***************************************************************************************************************
*/
int main() {
    cin >> N >> M;

    // nodes
    for (int i = 1; i <= N; ++i) {
        int p;
        cin >> p;

        Node node(i, p);
        NodeID_Node.emplace(i, node);
    }

    // edges
    Graph.resize(N + 1, vector<unordered_set<int>>(N + 1));
    for (int i = 1; i <= M; ++i) {
        int u, v;
        cin >> u >> v;

        Edge edge(i, u, v, capacity);
        EdgeID_Edge.emplace(i, edge);

        Graph[u][v].emplace(i);
        Graph[v][u].emplace(i);

        NodeID_Node[u].neighbors.emplace(v);
        NodeID_Node[v].neighbors.emplace(u);
    }

    // businesses
    int businessNum;
    cin >> businessNum;
    for (int i = 1; i <= businessNum; ++i) {
        int start, end, lenEdge, sW, eW,  v;
        cin >> start >> end >> lenEdge >> sW >> eW >> v;

        Business bus(i, start, end, sW, eW, v, lenEdge);
        for (int j = 0; j < lenEdge; ++j) {
            int edgeId;
            cin >> edgeId;

            bus.edgePath.emplace_back(edgeId);
            bus.edgePathCopy.emplace_back(edgeId);
        }

        ORIGIN_VALUE += bus.value;
        setNodePath(bus);
        costChannels(bus);
        BusID_Bus.emplace(i, bus);
    }
    currentValue = ORIGIN_VALUE;

    generateData();

    int T;
    cin >> T;
    double startTime = clock();
    for (int i = 0; i < T; ++i) {
        unordered_set<int> abandonedBusIds;
        while (true) {
            int failedEdgeId;
            cin >> failedEdgeId;
            if (failedEdgeId == -1) break;
            fixFailedEdge(failedEdgeId, abandonedBusIds);
        }
        back();
    }
    double endTime = clock();
    cout << (endTime - startTime) / 1000 << "s" << endl;
    cout << fixedCount << endl;
    cout << fixedValue << endl;
    cout << score << endl;
    return 0;
}